package dynamic.dpPack;

import java.util.Arrays;

/**
 * 完全背包
 */
public class CompetePack {

    // 最大价值 完全背包
    private int packCompeteDp(int V, int[] c, int[] w) {
        int[][] dp = new int[c.length+1][V+1];
        for (int i=1; i<=c.length; i++) {
            // 一定要从 1 开始。若j=c[i-1],c=2, 3, 4, 5, 1; V=4,导致结果错误
            for (int j=1; j<=V; j++) {
                if (j - c[i-1] >= 0) {
                    // 计算该点放下后的价值 dp[i][j-c[i-1]]+w[i-1]，该物品可能被多次计入
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-c[i-1]]+w[i-1]);
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
            System.out.println(Arrays.toString(dp[i]));
        }
        return dp[c.length][V];
    }

    private int packCompeteDpK(int V, int[] c, int[] w){
        int dp[][] = new int[c.length+1][V+1];
        int max = 0;
        for(int i = 1; i <=c.length; i++){
            for(int j = 1; j <= V; j++){
                for(int k = 0; k * c[i-1] <= j; k++){
                    int t = k * w[i-1] + dp[i - 1][j - k * c[i-1]];
                    if(max < t){
                        max = t;
                    }
                }
                dp[i][j] = max;
                //特别要注意max要重置为零,否则dp数组里面的值是错误的
                max = 0;
            }
            System.out.println(Arrays.toString(dp[i]));
        }
        return dp[c.length][V];
    }

    private int packCompeteDpOpt(int V, int[] c, int[] w) {
        int[] dp = new int[V+1];
        for (int i=1; i<=c.length; i++) {
            for (int j=c[i-1]; j<=V; j++) {
                dp[j] = Math.max(dp[j-c[i-1]]+w[i-1], dp[j]);
            }
            System.out.println(Arrays.toString(dp));
        }
        return dp[V];
    }

    private int packCompeteDpOpt1(int V, int[] c, int[] w) {
        int[] dp = new int[V+1];
        for (int i=1; i<=c.length; i++) {
            competePack(dp, V, c[i-1], w[i-1]);
            System.out.println(Arrays.toString(dp));
        }
        return dp[V];
    }

    public int competePack(int[] F, int V, int C, int W) {
        for (int j=C; j<=V; j++) {
            F[j] = Math.max(F[j-C]+W, F[j]);
        }
        return F[V];
    }

    //二进制分解法


    public static void main(String[] args) {
        int[] c = new int[]{2, 3, 4, 5, 1};  // 费用/重量
        int[] w = new int[]{6, 5, 4, 3, 2};  // 价值
        int V = 4;  // 背包容量
        CompetePack competePack = new CompetePack();
        int ans1 = competePack.packCompeteDp(V, c, w);
        System.out.println("dp:"+ans1);

        int ans4 = competePack.packCompeteDpK(V, c, w);
        System.out.println("dp k:"+ans4);

        int ans2 = competePack.packCompeteDpOpt(V, c, w);
        System.out.println("dp opt:"+ans2);

        int ans3 = competePack.packCompeteDpOpt1(V, c, w);
        System.out.println("dp opt1:"+ans3);
    }
}
